#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;
/**
 * 堆排序，自写
 */
void heap_adjust(vector<int> &v,int p){ //大顶堆调整
    int dad=p,son=p*2+1;
    int end=v.size();
    while(son<end){
        if(son+1<end && v[son]<v[son+1]){
            son+=1;
        }
        if(v[dad]>v[son]){
            return;
        }else{
            swap(v[dad],v[son]);
        }
    }
}

void heap_sort(vector<int> &v){
    int len=v.size();
    if(len<=0){
        return ;
    }
    for(int i=len/2-1;i>=0;i--){
        heap_adjust(v,i);
    }
    for(int i=len-1;i>0;i--){
        swap(v[0],v[i]);
        heap_adjust(v,0);
    }
}

/**
 * 大顶堆，用库函数
 */
void heap_sort2(vector<int> &v){
    int len=v.size();
    if(len<=0){
        return ;
    }
    make_heap(v.begin(),v.end(),less<int>());
    for(int i=len-1;i>0;i--){
        swap(v[0],v[i]);
        make_heap(v.begin(),v.begin()+i,less<int>());
    }
}

int main(){
    vector<int> v={3,2,4,56,87,98};

    heap_sort2(v);

    for(auto x:v){
        cout << x << " ";
    }cout << endl;



    return 0;
}